package com.leetcode_mianshi_150;

import com.sun.corba.se.impl.ior.NewObjectKeyTemplateBase;
import org.junit.Test;

import java.awt.*;
import java.awt.font.NumericShaper;
import java.util.*;
import java.util.List;


/**
 * @author: 临晖
 * @date: 2024/03/25
 * @description: LeetCode面试题150
 */
public class Solution {

    /**
     * 88. 合并两个有序数组
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * <p>
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 wordLen ，分别表示 nums1 和 nums2 中的元素数目。
     * <p>
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * <p>
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 wordCount + wordLen，其中前 wordCount 个元素表示应合并的元素，后 wordLen 个元素为 0 ，应忽略。nums2 的长度为 wordLen 。
     *
     * @param nums1
     * @param wordCount
     * @param nums2
     * @param wordLen
     */
    public void merge(int[] nums1, int wordCount, int[] nums2, int wordLen) {
        //方式一
        //for (int i = 0; i < wordLen; i++) {
        //    nums1[wordCount + i] = nums2[i];
        //}
        //
        //Arrays.sort(nums1);
        int i = wordCount - 1;
        int j = wordLen - 1;

        while (i >= 0 && j >= 0) {
            nums1[i + j + 1] = nums1[i] <= nums2[j] ? nums2[j--] : nums1[i--];
        }

        while (j >= 0) {
            nums1[i + j + 1] = nums2[j--];
        }
    }


    /**
     * 27. 移除元素
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int fast = 0;
        int last = 0;

        for (; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[last++] = nums[fast];
            }
        }


        return last;
    }


    /**
     * 26. 删除有序数组中的重复项
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int fast = 1;
        int last = 0;

        for (; fast < nums.length; fast++) {
            if (nums[fast] != nums[last]) {
                nums[++last] = nums[fast];
            }
        }

        return ++last;
    }


    /**
     * 80. 删除有序数组中的重复项 II
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {
        int fast = 1;
        int last = 0;
        int count = 1;
        //相等：
        //第一次：last++,第二次，不变
        //不相等：
        //last++，交换，
        for (; fast < nums.length; fast++) {
            if (nums[fast] == nums[last]) {
                if (count >= 2) {
                    continue;
                }
                nums[++last] = nums[fast];
                count++;
            } else {
                nums[++last] = nums[fast];
                count = 1;
            }

            //if (nums[fast] != nums[last] || count < 2) {
            //    nums[++last] = nums[fast];
            //    count = 1;
            //} else {
            //
            //    count++;
            //}
        }

        return ++last;
    }


    /**
     * 169. 多数元素
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个大小为 wordLen 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ wordLen/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            if (map.get(nums[i]) > nums.length / 2) {
                return nums[i];
            }
        }

        return 0;

        //return map.entrySet().stream().
        //        filter(o -> o.getValue() > nums.length / 2).
        //        findFirst().
        //        get().
        //        getKey();

    }


    /**
     * 189. 轮转数组
     * 尝试过
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * <p>
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int[] newNums = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int x = (i + k) % nums.length;
            newNums[x] = nums[i];
        }

        System.arraycopy(newNums, 0, nums, 0, nums.length);
    }


    /**
     * 121. 买卖股票的最佳时机
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int[][] dp = new int[prices.length][2];     //动态规划，持有股票，不持有股票

        dp[0][0] = -prices[0];


        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);      //持有股票有俩种状态，持续昨天的和今天新买入的
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        return dp[prices.length - 1][1];
    }


    /**
     * 122. 买卖股票的最佳时机 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        //贪心
        //int sum = 0;
        //for (int i = 1; i < prices.length; i++) {
        //    int wordCount = prices[i] - prices[i - 1];
        //    if (wordCount > 0) {
        //        sum += wordCount;
        //    }
        //}
        //
        //return sum;

        //动规
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        return dp[prices.length - 1][1];
    }


    /**
     * 55. 跳跃游戏
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * <p>
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * <p>
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        //if (nums.length == 0) {
        //    return true;
        //}
        //
        //if (nums[0] == 0) {
        //    if (nums.length == 1) {
        //        return true;
        //    } else {
        //        return false;
        //    }
        //}

        int end = 0;


        for (int i = 0; i <= end; i++) {
            if (end >= nums.length - 1) {
                return true;
            }

            end = Math.max(end, i + nums[i]);

        }


        return false;
    }


    /**
     * 45. 跳跃游戏 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * <p>
     * 给定一个长度为 wordLen 的 0 索引整数数组 nums。初始位置为 nums[0]。
     * <p>
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * <p>
     * 0 <= j <= nums[i]
     * i + j < wordLen
     * <p>
     * 返回到达 nums[wordLen - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[wordLen - 1]。
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {

        //if (nums.length == 1) {
        //    return 0;
        //}
        //
        ////贪心
        //int count = 0;
        //
        //int cover = 0;
        //int oldCover = 0;
        //
        //for (int i = 0; i <= cover; i++) {
        //    cover = Math.max(cover, i + nums[i]);
        //
        //
        //    if (i == oldCover) {
        //        count++;
        //        oldCover = cover;
        //
        //        if (cover >= nums.length - 1) {
        //            break;
        //        }
        //    }
        //}
        //
        //return count;

        //动态规划
        int[] dp = new int[nums.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }


        return dp[nums.length - 1];
    }


    /**
     * 274. H 指数
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
     * 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
     *
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        //Arrays.sort(citations);
        System.out.println(Integer.MAX_VALUE);

        int res = 0;
        for (int i = 0; i < citations.length; i++) {
            int ran = Math.min(citations[i], citations.length - i);
            res = Math.max(ran, res);

        }
        return res;

    }


    /**
     * 238. 除自身以外数组的乘积
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     * 请 不要使用除法，且在 O(wordLen) 时间复杂度内完成此题。
     *
     * @param nums
     * @return
     */
    //假如nums为[1,2,3,4]，那么answer的值分别为[(2,3,4),(1,3,4),(1,2,4),(1,2,3)]
    //如果吧i当前值相乘的时候看做是1那么就有如下样式
    //  1, 2, 3, 4
    //  1, 1, 3, 4
    //  1, 2, 1, 4
    //  1, 2, 3, 1
    // 他的对角线1将他们分割成了两个三角形，对于answer的元素，
    //我们可以先计算一个三角形每行的乘积，然后再去计算另外一个三角形每行的乘积，
    //然后各行相乘，就是answer每个对应的元素
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;

        int[] anwser = new int[len];
        anwser[0] = 1;      //nums[0]的前缀积为1

        for (int i = 1; i < len; i++) {         //将每个值的前缀积都算出来
            anwser[i] = anwser[i - 1] * nums[i - 1];
        }


        //开始计算后缀积 * 前缀积
        int temp = 1;           //最后一个值的默认后缀积为1，然后他的前缀积是answer[len - 1];
        anwser[len - 1] = temp * anwser[len - 1];           //所以：最后一个数字等于他的前缀积 * 后最积
        for (int i = len - 2; len >= 0; i--) {
            temp = nums[i - 1] * temp;      //以此类推，每一次循环，temp就是下一个数的后最积
            anwser[i] = temp * anwser[i];
        }
        return anwser;

    }


    /**
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     * <p>
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     * <p>
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给定一个罗马数字，将其转换成整数。
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {


        int sum = 0;
        int preNum = getValue(s.charAt(0));


        for (int i = 1; i < s.length(); i++) {
            int nextNum = getValue(s.charAt(i));

            if (preNum < nextNum) {
                sum -= preNum;
            } else {
                sum += preNum;
            }

            preNum = nextNum;

        }

        sum += preNum;

        return sum;
    }

    private int getValue(char ch) {
        switch (ch) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }


    /**
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给你一个整数，将其转为罗马数字
     *
     * @param num
     * @return
     */
    int allNum = 0;

    public String intToRoman(int num) {
        allNum = num;
        String res = "";

        while (allNum != 0) {
            res += getString();
        }

        return res;

    }

    private String getString() {
        int[] arr = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] aws = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        for (int i = 0; i < arr.length; i++) {
            if (allNum >= arr[i]) {
                allNum -= arr[i];
                return aws[i];
            }
        }

        return "";
    }


    /**
     * 58. 最后一个单词的长度
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
     * 单词 是指仅由字母组成、不包含任何空格字符的最大
     * 子字符串
     *
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        int len = s.length();


        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char op = s.charAt(i);
            if (i > 0 && s.charAt(i - 1) == ' ' && isChar(op)) {      //当前字符是字母，前一个是空格，重新计数
                count = 1;
            } else if (isChar(op)) {
                count++;
            }
        }

        return count;
    }

    public boolean isChar(char op) {
        if (op >= 'a' && op <= 'z' || op >= 'A' && op <= 'Z') {
            return true;
        }

        return false;
    }


    /**
     * 14. 最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {

        //纵向
        //String pubStr = "";
        //
        //
        //for (int i = 0; i < strs[0].length(); i++) {            //第一个单词得长度
        //    char op = strs[0].charAt(i);
        //   for (int j = 1; j < strs.length; j++) {      //除去第一个单词得其它单词
        //       if (i >= strs[i].length() || strs[j].charAt(i) != op) {
        //           return pubStr;
        //       }
        //   }
        //
        //   pubStr += op;
        //}
        //
        //return pubStr;

        //横向

        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];
        int count = strs.length;

        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
        }

        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int len = Math.min(str1.length(), str2.length());
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (str1.charAt(i) == str2.charAt(i)) {
                index++;
            } else {
                break;
            }
        }

        return str1.substring(0, index);
    }


    /**
     * 6. Z 字形变换
     * 中等
     * 相关标签
     * 相关企业
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     *
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {

        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }

        //摆动轮数
        int len = s.length();


        //int wheeledNum = (len + numRows) / numRows;
        char[][] chars = new char[numRows][len];


        boolean falg = true;        //标识方向
        int index = 0;      //列
        int start = 1;
        while (true) {
            if (falg) {
                for (int i = 1; i < numRows; i++) {
                    chars[i][index] = s.charAt(start++);
                    if (start >= len) {
                        break;
                    }
                }
            } else {
                for (int i = numRows - 2; i >= 0; i--) {
                    chars[i][++index] = s.charAt(start++);
                    if (start >= len) {
                        break;
                    }
                }
            }

            falg = !falg;
            if (start >= len) {
                break;
            }
        }

        String res = "" + s.charAt(0);
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                if (chars[i][j] != '\u0000') {
                    res += chars[i][j];
                }

            }
        }

        return res;

    }


    /**
     * 68. 文本左右对齐
     * 困难
     * 相关标签
     * 相关企业
     * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
     * <p>
     * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
     * <p>
     * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
     * <p>
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
     *
     * @param words
     * @param maxWidth
     * @return
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        ArrayList<String> res = new ArrayList<>();
        int currWordLen = 0;
        int start = 0;

        for (int i = 0; i < words.length; i++) {
            currWordLen += (words[i].length() + 1);

            if (i + 1 >= words.length || currWordLen + words[i + 1].length() > maxWidth) {        //当前单词是最后一个单词，且没有超出
                res.add(fillWords(words, start, i, maxWidth, i + 1 >= words.length));       //加入

                start = i + 1;      //当前行其实单词的下标
                currWordLen = 0;        //置零，到了下一行了要
            }
        }

        return res;
    }

    /**
     * 对每行单词进行空格平均划分
     */
    private String fillWords(String[] words, int bg, int ed, int maxWidth, boolean lastLine) {
        //计算单词个数
        int wordNum = ed - bg + 1;
        //给每个单词分配一个空格，最后一个不需要
        //int spaceNum = maxWidth - (wordNum - 1);
        int spaceNum = maxWidth;

        //剩下的使用单词占位
        for (int i = bg; i <= ed; i++) {
            spaceNum -= words[i].length();
        }

        //到了这里，还剩下的空格，用于平均分配给每个单词
        //平均分配过后，还剩余的空格分配给前边的每个单词
        int spaceAvg = wordNum == 1 ? 1 : spaceNum / (wordNum - 1);
        int spaceRan = wordNum == 1 ? 0 : spaceNum % (wordNum - 1);

        //这里 bg != ed，是因为，最后一个单词，最后添加
        StringBuilder sb = new StringBuilder();
        for (int i = bg; i < ed; i++) {
            sb.append(words[i]);

            //如果是最后一行的话，每个单词中间空一个空格，最后的空白由空格补位
            if (lastLine) {
                sb.append(" ");
                continue;
            }

            //本身的一个单词，平均分配的单词，还有多余的单词
            int wordInter = 0;
            if (spaceRan > 0) {
                wordInter = spaceAvg + 1;
                spaceRan--;
            } else {
                wordInter = spaceAvg;
            }

            while (wordInter-- > 0) {
                sb.append(" ");
            }
        }

        //现在还剩下最后一个单词
        //如果是最后一行
        sb.append(words[ed]);
        if (lastLine || wordNum == 1) {
            int last = maxWidth - sb.length();
            while (last-- > 0) {
                sb.append(" ");
            }
        }
        //如果不是最后一行

        return sb.toString();
    }

    //public List<String> fullJustify(String[] words, int maxWidth) {
    //    List<String> res = new ArrayList<>();
    //    int cnt = 0, bg = 0;
    //    for (int i = 0; i < words.length; i++) {
    //        cnt += words[i].length() + 1;
    //        // 如果是最后一个单词，或者加上下一个词就超过长度了，即可凑成一行
    //        if (i + 1 == words.length || cnt + words[i + 1].length() > maxWidth) {
    //            // 对每行单词进行空格平均划分
    //            res.add(fillWords(words, bg, i, maxWidth, i + 1 == words.length));
    //            bg = i + 1;
    //            cnt = 0;
    //        }
    //    }
    //    return res;
    //}

    ///**
    // * 对每行单词进行空格平均划分
    // */
    //private String fillWords(String[] words, int bg, int ed, int maxWidth, boolean lastLine) {
    //    int wordCount = ed - bg + 1;
    //    // 除去每个单词尾部空格， + 1 是最后一个单词的尾部空格的特殊处理
    //    int spaceCount = maxWidth + 1 - wordCount;
    //    for (int i = bg; i <= ed; i++) {
    //        // 除去所有单词的长度
    //        spaceCount -= words[i].length();
    //    }
    //    // 词尾空格
    //    int spaceSuffix = 1;
    //    // 额外空格的平均值 = 总空格数/间隙数
    //    int spaceAvg = (wordCount == 1) ? 1 : spaceCount / (wordCount - 1);
    //    // 额外空格的余数
    //    int spaceExtra = (wordCount == 1) ? 0 : spaceCount % (wordCount - 1);
    //    // 填入单词
    //    StringBuilder sb = new StringBuilder();
    //    for (int i = bg; i < ed; i++) {
    //        sb.append(words[i]);
    //        if (lastLine) {
    //            sb.append(" ");
    //            continue;
    //        }
    //        int wordLen = 0;
    //        //平均分配空格后，还剩余的空格肯定是不足平均分配，因此，给前几个单词分配给就行
    //        if (spaceExtra > 0) {
    //            wordLen = spaceSuffix + spaceAvg + 1;
    //            spaceExtra--;
    //        } else {
    //            wordLen = spaceSuffix + spaceAvg;
    //        }
    //
    //        while (wordLen-- > 0) {
    //            sb.append(" ");
    //        }
    //    }
    //    // 填入最后一个单词
    //    sb.append(words[ed]);
    //    // 补上这一行最后的空格
    //    int lastSpaceCnt = maxWidth - sb.length();
    //    while (lastSpaceCnt-- > 0) {
    //        sb.append(" ");
    //    }
    //    return sb.toString();
    //}


    /**
     * 125. 验证回文串
     * 简单
     * 相关标签
     * 相关企业
     * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
     * 字母和数字都属于字母数字字符。
     * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        char[] arr = s.toCharArray();
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] >= 'a' && arr[i] <= 'z') || (arr[i] >= 'A' && arr[i] <= 'Z') || (arr[i] >= '0' && arr[i] <= '9')) {
                str.append(arr[i]);
            }

        }

        if (isWhether(str.toString().toUpperCase())) {
            return true;
        }

        return false;

    }


    /**
     * 判断是否为回文子串
     *
     * @param str
     * @return
     */
    public boolean isWhether(String str) {
        int begin = 0;
        int end = str.length() - 1;

        while (begin <= end) {
            if (str.charAt(begin) != str.charAt(end)) {
                return false;
            }
            begin++;
            end--;
        }

        return true;
    }


    /**
     * 167. 两数之和 II - 输入有序数组
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
     * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     * 你所设计的解决方案必须只使用常量级的额外空间。
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        //方法一
        //int beg = 0;
        //int end = numbers.length - 1;
        //int[] res = new int[2];
        //
        //while (beg <= end) {
        //
        //    int temp = numbers[beg] + numbers[end];
        //    if (temp == target) {
        //        res[0] = beg + 1;
        //        res[1] = end + 1;
        //        break;
        //    } else if (temp > target) {
        //        end--;
        //    } else {
        //        beg++;
        //    }
        //}
        //
        //return res;

        //方法二

        int[] res = new int[2];

        //当前值，下标
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(target - numbers[0], 0);
        for (int i = 1; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                res[0] = map.get(numbers[i]) + 1;
                res[1] = i + 1;
                break;
            }
            map.put(target - numbers[i], i);
        }

        return res;
    }


    /**
     * 30. 串联所有单词的子串
     * 困难
     * 相关标签
     * 相关企业
     * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
     * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
     * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
     * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
     *
     * @param s
     * @param words
     * @return
     */
    //public List<Integer> findSubstring(String s, String[] words) {
    //    ArrayList<Integer> res = new ArrayList<>();
    //    if (s == null || s.length() == 0 || words.length == 0) {
    //        return res;
    //    }
    //
    //
    //    int count = words.length;
    //    int wordLen = words[0].length();
    //    int talLen = count * wordLen;
    //
    //    if (s.length() < wordLen) {
    //        return res;
    //    }
    //
    //
    //    int startIndex = 0;
    //
    //    for (int i = startIndex; i <= s.length() - talLen; i++) {
    //        String temp = s.substring(i, i + talLen);
    //        boolean flag = true;
    //
    //
    //        HashMap<String, Integer> map = new HashMap<>();
    //        for (int wordCount = 0; wordCount <= i + talLen - wordLen; wordCount += wordLen) {
    //            String s1 = temp.substring(wordCount, wordCount + wordLen);
    //            map.put(s1, map.getOrDefault(s1, 0) + 1);
    //        }
    //
    //
    //        for (int j = 0; j < words.length; j++) {
    //            if (map.containsKey(words[j])) {
    //                Integer num = map.get(words[j]);
    //                num--;
    //                if (num == 0) {
    //                    map.remove(words[j]);
    //                } else {
    //                    map.put(words[j], num);
    //                }
    //            } else {
    //                break;
    //            }
    //        }
    //
    //        //map全部包含，且map最后一定为空
    //        if (map.isEmpty()) {
    //            res.add(i);
    //            startIndex = i + talLen;
    //        }
    //    }
    //
    //    return res;
    //
    //}
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int ls = s.length();
        int wordLen = words[0].length();
        int wordCount = words.length;
        // 预处理移动 0 ~ n - 1个字符
        for (int i = 0; i < wordLen; ++i) {
            // 如果剩余的字符串不够检验了就结束
            if (i > ls - wordLen * wordCount)
                break;
            // 该窗口的单词和words里的差值
            Map<String, Integer> diff = new HashMap<>();
            // 先给一个长度为words的窗口，开始该预处理条件下的滑动窗口
            for (int j = 0; j < wordCount; ++j) {
                String temp = s.substring(i + j * wordLen, i + j * wordLen + wordLen);
                diff.put(temp, diff.getOrDefault(temp, 0) + 1);
            }
            // 看看该窗口与words差多少
            for (String word : words) {
                diff.put(word, diff.getOrDefault(word, 0) - 1);
                if (diff.get(word).equals(0))
                    diff.remove(word);
            }
            // 开始滑动窗口
            for (int start = i; start < ls - wordLen * wordCount + 1; start += wordLen) {
                // 先不加单词，先用下面的判断语句判断是否该窗口符合条件
                if (start != i) {
                    String temp = s.substring(start + wordLen * (wordCount - 1), start + wordLen * wordCount);
                    diff.put(temp, diff.getOrDefault(temp, 0) + 1);
                    if (diff.get(temp).equals(0)) {
                        diff.remove(temp);
                    }
                    temp = s.substring(start - wordLen, start);
                    diff.put(temp, diff.getOrDefault(temp, 0) - 1);
                    if (diff.get(temp).equals(0)) {
                        diff.remove(temp);
                    }
                }
                // 没有差别就将该下标放到该哈希表中
                if (diff.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }


    /**
     * 36. 有效的数独
     * 中等
     * 相关标签
     * 相关企业
     * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char op = board[i][j];

                if (op >= '0' && op <= '9') {
                    if (!isRowOrCol(i, j, board, op) || !isNeig(i, j, board, op)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }


    /**
     * 判断是否在同一行或同一列
     *
     * @param x
     * @param y
     * @param board
     * @param op
     * @return
     */
    public boolean isRowOrCol(int x, int y, char[][] board, char op) {
        for (int i = 0; i < board.length; i++) {        //行
            if (i != x && board[i][y] >= '0' && board[i][y] <= '9' && op == board[i][y]) {
                return false;
            }
        }

        for (int j = 0; j < board[x].length; j++) {
            if (j != y && board[x][j] >= '0' && board[x][j] <= '9' && op == board[x][j]) {
                return false;
            }
        }

        return true;


    }

    public boolean isNeig(int x, int y, char[][] board, char op) {
        int row = x / 3 * 3;
        int col = y / 3 * 3;

        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if ((i != x || j != y) && board[i][j] >= '0' && board[i][j] <= '9' && board[i][j] == op) {
                    return false;
                }
            }
        }

        return true;
    }


    /**
     * 48. 旋转图像
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        if (matrix == null || len == 1) {
            return;
        }


        int[][] orgMatrix = new int[len][len];

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                orgMatrix[i][j] = matrix[i][j];
            }
        }


        for (int j = len - 1; j >= 0; j--) {
            for (int i = 0; i < len; i++) {
                matrix[i][j] = orgMatrix[len - 1 - j][i];
            }
        }


    }


    /**
     * 73. 矩阵置零
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        if (matrix == null) {
            return;
        }

        int m = matrix.length;
        int n = matrix[0].length;


        boolean[][] isVisted = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {

                    if (!isVisted[i][j]) {
                        reZeroes(matrix, isVisted, i, j);
                    }

                }
            }
        }
    }

    public void reZeroes(int[][] matrix, boolean[][] isVisted, int x, int y) {
        isVisted[x][y] = true;

        int m = matrix.length;
        int n = matrix[0].length;


        for (int j = 0; j < n; j++) {
            if (!isVisted[x][j] && matrix[x][j] != 0) {
                matrix[x][j] = 0;
                isVisted[x][j] = true;
            }

        }


        for (int i = 0; i < m; i++) {
            if (!isVisted[i][y] && matrix[i][y] != 0) {
                matrix[i][y] = 0;
                isVisted[i][y] = true;
            }
        }
    }


    /**
     * 289. 生命游戏
     * 中等
     * 相关标签
     * 相关企业
     * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
     * <p>
     * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
     * <p>
     * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
     *
     * @param board
     */
    public void gameOfLife(int[][] board) {
        //分析，
        // 小于俩个，1->0
        //等于2个，
        // 等于3个，0->1
        // 大于于4个，1->0
        //大于四个

        int m = board.length;
        int n = board[0].length;

        int[][] goalBoard = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = count(board, i, j, m, n);

                if (num < 2) {
                    goalBoard[i][j] = 0;
                } else if (num == 2) {
                    goalBoard[i][j] = board[i][j];
                } else if (num == 3) {
                    goalBoard[i][j] = 1;
                } else if (num > 3) {
                    goalBoard[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = goalBoard[i][j];
            }
        }
    }

    public int count(int[][] board, int x, int y, int m, int n) {
        int num = 0;

        int[][] direction = {
                {0, 1}, {1, 0}, {1, 1},
                {1, -1},
                {-1, 1},
                {0, -1}, {-1, 0}, {-1, -1}
        };


        for (int i = 0; i < 8; i++) {
            int tempX = x + direction[i][0];
            int tempY = y + direction[i][1];

            if (tempX >= m || tempX < 0 || tempY >= n || tempY < 0) {
                continue;
            }

            if (board[tempX][tempY] == 1) {
                num++;
            }
        }

        return num;
    }


    /**
     * 205. 同构字符串
     * 简单
     * 相关标签
     * 相关企业
     * 给定两个字符串 s 和 t ，判断它们是否是同构的。
     * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
     * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (map.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            } else if (map.containsValue(t.charAt(i))) {
                return false;
            } else {
                map.put(s.charAt(i), t.charAt(i));

            }
        }

        return true;
    }


    /**
     * 290. 单词规律
     * 简单
     * 相关标签
     * 相关企业
     * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
     * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
     *
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern(String pattern, String s) {
        String[] arr = s.split(" ");

        HashMap<Character, String> map = new HashMap<>();

        if (pattern.length() != arr.length) {
            return false;
        }

        for (int i = 0; i < pattern.length(); i++) {
            if (map.containsKey(pattern.charAt(i))) {
                if (!map.get(pattern.charAt(i)).equals(arr[i])) {
                    return false;
                }
            } else if (map.containsValue(arr[i])) {
                return false;
            } else {
                map.put(pattern.charAt(i), arr[i]);
            }
        }
        return true;
    }


    /**
     * 219. 存在重复元素 II
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();


        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (Math.abs(i - map.get(nums[i])) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);

        }

        return false;
    }


    /**
     * 228. 汇总区间
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个  无重复元素 的 有序 整数数组 nums 。
     * 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
     * 列表中的每个区间范围 [a,b] 应该按如下格式输出：
     *
     * @param nums
     * @return
     */
    public List<String> summaryRanges(int[] nums) {


        ArrayList<String> res = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return res;
        }

        int start = nums[0];
        int end = nums[0];


        for (int i = 1; i < nums.length; i++) {
            if (end + 1 != nums[i]) {
                res.add(start == end ? start + "" : start + "->" + end);
                start = nums[i];
                end = nums[i];
            } else {
                end++;
            }
        }

        res.add(start == end ? start + "" : start + "->" + end);

        return res;
    }


    /**
     * 57. 插入区间
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
     * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
     * 返回插入之后的 intervals。
     * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
     *
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int begin = newInterval[0];
        int end = newInterval[1];

        ArrayList<int[]> list = new ArrayList<>();

        boolean flag = false;
        for (int[] interval : intervals) {
            if (end < interval[0]) {
                if (!flag) {
                    list.add(new int[]{begin, end});
                    flag = true;
                }
                list.add(interval);
            } else if (begin > interval[1]) {
                list.add(interval);
            } else {
                begin = Math.min(begin, interval[0]);
                end = Math.max(end, interval[1]);
            }
        }

        if (!flag) {
            list.add(new int[]{begin, end});
        }

        return list.toArray(new int[][]{});
    }


    /**
     * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
     * <p>
     * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）
     *
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        String[] arr = path.split("/+");
        StringBuilder str = new StringBuilder();

        //str.append("/");

        LinkedList<String> stack = new LinkedList<>();


        for (int i = 1; i < arr.length; i++) {

            if (arr[i].equals(".")) {

            } else if (arr[i].equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }

            } else {
                stack.addLast(arr[i]);
            }
        }


        if (stack.isEmpty()) {
            str.append("/");
        }

        while (!stack.isEmpty()) {
            str.append("/" + stack.pollFirst());
        }


        return str.toString();
    }


    public int calculate(String s) {
        Deque<Integer> ops = new LinkedList<Integer>();     //栈顶元素表示当前运算符得正负
        ops.push(1);        //假设当前运算符是 +
        int sign = 1;


        int i = 0;
        int len = s.length();
        int res = 0;

        while (i < len) {
            char op = s.charAt(i);

            if (op == ' ') {
                i++;
            } else if (op == '+') {
                sign = ops.peek();
                i++;
            } else if (op == '-') {
                sign = -ops.peek();
                i++;
            } else if (op == '(') {
                ops.push(sign);
                i++;
            } else if (op == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;


                while (i < len && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }

                res += num * sign;
            }
        }

        return res;

    }


    /**
     * 224. 基本计算器
     * 困难
     * 相关标签
     * 相关企业
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
     *
     * @param s
     * @return
     */
    //public int calculate(String s) {
    //
    //    int res = 0;        //计算结果
    //    Stack<String> stack = new Stack<>();
    //    for (int i = 0; i < s.length(); i++) {
    //        char op = s.charAt(i);
    //        if (op == '+' || op == '(' || op == '-') {            //加   --   左括号   -- 减
    //            stack.push(op+ "");
    //        } else if (op == ')'){      //右
    //            String number1 = stack.pop();
    //            String number = "";
    //            if ("-".equals(stack.peek())) {
    //                stack.pop();
    //                //number1 = "-" + number1;        //弹出符号
    //                stack.pop();        //弹出括号
    //
    //                if (stack.isEmpty()) {
    //                    stack.push("-");
    //                    stack.push(number1);
    //                    continue;
    //                }
    //
    //                String operator  = stack.pop();          //弹出操作符
    //                String number2 = stack.pop();
    //
    //                if ("+".equals(operator)) {
    //
    //                    if (Integer.parseInt(number2) - Integer.parseInt(number1) > 0) {
    //                        number = Integer.parseInt(number2) - Integer.parseInt(number1) + "";
    //                    } else {
    //                        stack.push("-");
    //                        number = Math.abs(Integer.parseInt(number2) - Integer.parseInt(number1)) + "";
    //                    }
    //                } else if ("-".equals(operator)) {
    //                    number = Integer.parseInt(number1) + Integer.parseInt(number2) + "";
    //                }
    //            } else {
    //                stack.pop();        //弹出括号
    //
    //                if (stack.isEmpty()) {
    //                    stack.push(number1);
    //                    continue;
    //                }
    //
    //                String operator  = stack.pop();        //弹出符号
    //                if (stack.isEmpty()) {
    //                    stack.push(operator);
    //                    stack.push(number1);
    //                    continue;
    //                }
    //
    //                String number2 = stack.pop();       //判断number2是不是为负数
    //                if (!stack.isEmpty() && "-".equals(stack.peek())) {         //判断当前数是不是负数
    //                    stack.pop();
    //                    number2 = "-" + number2;
    //                }
    //
    //                if ("+".equals(operator)) {
    //                    number = Integer.parseInt(number1) + Integer.parseInt(number2) + "";
    //                } else if ("-".equals(operator)) {
    //                    if (Integer.parseInt(number2) - Integer.parseInt(number1) >= 0) {
    //                        number = Integer.parseInt(number2) - Integer.parseInt(number1) + "";
    //                    } else {
    //                        stack.push("-");
    //                        number = Math.abs(Integer.parseInt(number2) - Integer.parseInt(number1)) + "";
    //                    }
    //                }
    //            }
    //
    //            stack.push(number);
    //
    //        } else if (op >= '0' && op <= '9'){        //数字
    //            String number1 = op + "";
    //            while (i < s.length() - 1&& s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
    //                number1 += s.charAt(i + 1);
    //                i++;
    //            }
    //
    //            if (stack.isEmpty() || "(".equals(stack.peek())) {          //第一次入栈
    //                stack.push(number1);
    //                continue;
    //            }
    //
    //            String operator = stack.pop();
    //
    //            if (stack.isEmpty() || "(".equals(stack.peek())) {
    //                stack.push(operator);       //重新加入操作符
    //                stack.push(number1);        //加入当前数字
    //                continue;
    //            }
    //
    //
    //            String number2 = stack.pop();
    //            if (!stack.isEmpty() && "-".equals(stack.peek())) {         //判断当前数是不是负数
    //                stack.pop();
    //                number2 = "-" + number2;
    //            }
    //
    //            String number = "";
    //            if ("+".equals(operator)) {
    //                number = Integer.parseInt(number1) + Integer.parseInt(number2) + "";
    //            } else if ("-".equals(operator)) {
    //                if (Integer.parseInt(number2) - Integer.parseInt(number1) >= 0) {
    //                    number = Integer.parseInt(number2) - Integer.parseInt(number1) + "";
    //                } else {
    //                    stack.push("-");
    //                    number = Math.abs(Integer.parseInt(number2) - Integer.parseInt(number1)) + "";
    //                }
    //            }
    //
    //            stack.push(number);
    //
    //        }
    //    }
    //
    //    String number = stack.pop();
    //    if (!stack.isEmpty()) {
    //        number = "-" + number;
    //    }
    //    res = Integer.parseInt(number);
    //    return res;
    //}


    //String temp = stack.peek();
    //stack.push(op + "");
    //if (stack.isEmpty() || "(".equals(temp)) {      //如果栈为空，或则碰到左括号，则，当作一元运算符
    //
    //}


    /**
     * 2. 两数相加
     * 中等
     * 相关标签
     * 相关企业
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * <p>
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {


        ListNode first = new ListNode();
        ListNode currNode = first;

        int sum = 0;
        int remainder = 0;
        while (true) {
            if (l1 == null) {
                currNode.next = l2;
                break;
            }

            if (l2 == null) {
                currNode.next = l1;
                break;
            }

            sum = l1.val + l2.val + remainder;
            remainder = 0;
            ListNode node = new ListNode();
            if (sum % 10 - sum == 0) {      //表示小于十
                node.val = sum;
            } else {        //表示大于十
                node.val = sum % 10;
                remainder = sum / 10;
            }

            currNode.next = node;
            currNode = node;

            l1 = l1.next;
            l2 = l2.next;

        }

        while (currNode.next != null && remainder != 0) {
            currNode = currNode.next;
            sum = currNode.val + remainder;

            if (sum % 10 - sum == 0) {      //表示小于十
                currNode.val = sum;
                remainder = 0;
            } else {        //表示大于十
                currNode.val = sum % 10;
                remainder = sum / 10;
            }
        }

        if (currNode.next == null && remainder != 0) {

            currNode.next = new ListNode(remainder);
        }

        return first.next;

    }


    /**
     * 21. 合并两个有序链表
     * 简单
     * 相关标签
     * 相关企业
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (list1 == null) {
            return list2;
        }

        if (list2 == null) {
            return list1;
        }

        ListNode head = new ListNode();

        ListNode curr = head;
        ListNode next = head;

        while (true) {
            if (list1.val < list2.val) {
                curr.next = list1;

                if (list1.next == null) {
                    list1.next = list2;
                    break;
                }

                list1 = list1.next;

            } else {
                curr.next = list2;

                if (list2.next == null) {
                    list2.next = list1;
                    break;
                }

                list2 = list2.next;
            }

            curr = curr.next;

        }

        return head.next;
    }


    /**
     * 138. 随机链表的复制
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random
     * 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
     *
     * @param head
     * @return
     */
    //public Node copyRandomList(Node head) {
    //
    //    HashMap<Integer, Node> map = new HashMap<>();
    //
    //    Node first = new Node(head.val);
    //    Node curr = first;
    //
    //    if (head.random != null) {
    //
    //    }
    //
    //    Node curr2 = head.next;
    //    while (curr2 != null) {
    //        Node node = new Node(curr2.val);
    //        curr.next = node;
    //
    //        curr = node;
    //        curr2 = curr2.next;
    //
    //    }
    //
    //    curr2
    //
    //    return head;
    //}

    //todo 非常惊艳的一种方式！！！！！！！！！！！！！！巨推荐！！！！！！！！！！
    //public Node copyRandomList(Node head) {
    //    if (head == null) {
    //        return head;
    //    }
    //
    //    Node curr = head;
    //    HashMap<Node, Node> map = new HashMap<>();
    //    while (curr != null) {
    //        map.put(curr, new Node(curr.val));
    //        curr = curr.next;
    //    }
    //
    //    curr = head;
    //
    //    while (curr != null) {
    //        map.get(curr).next = map.get(curr.next);
    //        map.get(curr).random = map.get(curr.random);
    //        curr = curr.next;
    //    }
    //
    //    return map.get(head);
    //}
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node curr = head;

        //拼接新的列表  ---  (新的节点在旧的节点后面,下面要用)
        while (curr.next != null) {
            Node temp = new Node(curr.val);
            temp.next = curr.next;
            curr.next = temp;
            curr = temp.next;
        }


        curr = head;
        while (curr.next != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }

            curr = curr.next.next;
        }

        //拆开
        curr = head.next;
        Node pre = head;
        Node res = head.next;

        while (curr.next != null) {
            pre.next = pre.next.next;
            curr.next = curr.next.next;
            pre = pre.next;
            curr = curr.next;
        }

        return res;

    }


    /**
     * 92. 反转链表 II
     * 中等
     * 相关标签
     * 相关企业
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (head == null || left == right) {
            return head;
        }


        ListNode leftNode = null;
        ListNode rightNode = null;

        ListNode curr = head;
        int count = 1;

        HashMap<Integer, ListNode> map = new HashMap<>();

        while (curr != null) {
            if (count >= left && count <= right) {
                map.put(count, curr);
            }
            //记录左边节点
            if (count == left - 1) {
                leftNode = curr;
            }

            //记录右边节点
            if (count == right + 1) {
                rightNode = curr;
                break;
            }

            curr = curr.next;
            count++;

        }

        for (int i = right; i > left; i--) {
            map.get(i).next = map.get(i - 1);
        }

        if (leftNode == null && rightNode == null) {
            map.get(left).next = null;
            return map.get(right);
        } else if (leftNode == null && rightNode != null) {
            map.get(left).next = rightNode;
            return map.get(right);
        } else if (leftNode != null && rightNode == null) {
            leftNode.next = map.get(right);
            map.get(left).next = null;
            return head;
        } else {
            leftNode.next = map.get(right);
            map.get(left).next = rightNode;
            return head;
        }


    }


    /**
     * 25. K 个一组翻转链表
     * 困难
     * 相关标签
     * 相关企业
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode first = new ListNode(0);

        //下标 -- 节点
        HashMap<Integer, ListNode> map = new HashMap<>();

        //记录节点数量
        int nodeCount = 0;

        //辅助指指针
        ListNode curr = head;

        while (curr != null) {
            nodeCount++;
            map.put(nodeCount, new ListNode(curr.val));

            curr = curr.next;
        }

        //记录循环次数
        int loopCount = nodeCount / k;
        curr = first;

        for (int i = 1; i <= loopCount; i++) {
            int begin = (i - 1) * k + 1;
            int end = i * k;

            curr.next = reverList(map, begin, end);

            //将curr移动到最后一个节点
            while (curr.next != null) {
                curr = curr.next;
            }
        }

        if (loopCount * k < nodeCount) {
            for (int i = loopCount * k + 1; i <= nodeCount; i++) {
                curr.next = map.get(i);
                curr = curr.next;
            }
        }

        return first.next;

    }

    /**
     * 反转链表
     *
     * @param map
     * @param begin
     * @param end
     * @return
     */
    public ListNode reverList(Map<Integer, ListNode> map, int begin, int end) {
        for (int i = end; i > begin; i--) {
            map.get(i).next = map.get(i - 1);
        }
        return map.get(end);
    }


    /**
     * 82. 删除排序链表中的重复元素 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        //todo 又是一个非常惊艳的解决办法！！！！！！！！！！！！！！！！！！！！！！！！！！
        //定义哨兵节点
        ListNode dummy = new ListNode(0, head);

        ListNode curr = dummy;

        while (curr.next != null && curr.next.next != null) {
            int val = curr.next.val;

            if (curr.next.next.val == val) {
                while (curr.next != null && curr.next.val == val) {
                    curr.next = curr.next.next;
                }

            } else {
                curr = curr.next;
            }
        }

        return dummy.next;
    }


    /**
     * 61. 旋转链表
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        //方法一
        //if (head == null || head.next == null) {
        //    return head;
        //}
        //
        ////节点计数
        //int nodeCount = 0;
        ////辅助节点
        //ListNode curr = head;
        //
        //while (curr != null) {
        //    nodeCount++;
        //    curr = curr.next;
        //}
        //
        //k %= nodeCount;
        //if (k == 0) {
        //    return head;
        //}
        //
        //ArrayList<ListNode> temp = new ArrayList<>();
        //
        //int count = 1;
        //
        //curr = head;
        //while (count <= nodeCount - k) {
        //    temp.add(new ListNode(curr.val));
        //    count++;
        //    curr = curr.next;
        //}
        //
        //head = curr;
        //while (curr.next != null) {
        //    curr = curr.next;
        //}
        //
        //while (temp.size() != 0) {
        //    curr.next = temp.get(0);
        //    temp.remove(0);
        //    curr = curr.next;
        //}
        //
        //return head;

        //方法二
        if (head == null) {
            return head;
        }

        //节点计数
        int nodeCount = 0;
        //辅助节点
        ListNode curr = head;

        while (curr != null) {
            nodeCount++;
            curr = curr.next;
        }

        k %= nodeCount;
        if (k == 0) {
            return head;
        }

        curr = head;
        //本质：将后面的k个节点放到最后面
        int frontNodeCount = nodeCount - k;
        for (int i = 0; i < frontNodeCount - 1; i++) {
            curr = curr.next;
        }
        ListNode newHead = curr.next;
        curr.next = null;
        curr = newHead;

        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = head;


        return newHead;


    }


    /**
     * 86. 分隔链表
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }

        ListNode dummy1 = new ListNode(0, head);
        ListNode dummy2 = new ListNode(0);
        ListNode curr1 = dummy1;
        ListNode curr2 = dummy2;

        while (curr1.next != null) {
            if (curr1.next.val < x) {
                curr2.next = curr1.next;
                curr2 = curr2.next;

                curr1.next = curr1.next.next;
            } else {
                curr1 = curr1.next;
            }
        }

        curr2.next = dummy1.next;

        return dummy2.next;
    }


    /**
     * 114. 二叉树展开为链表
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        //方法一，  21%
        //if (root == null || (root.left == null && root.right == null)) {
        //    return;
        //}
        //
        //ArrayList<TreeNode> list = new ArrayList<>();
        //pre(root, list);
        //
        //TreeNode curr = root;
        //while (list.size() !=0) {
        //    curr.right = list.get(0);
        //    curr.left = null;
        //    curr = curr.right;
        //
        //    list.remove(0);
        //}

        //方法二  100%
        while (root != null) {
            if (root.left == null) {
                root = root.right;
            } else {
                TreeNode curr = root.left;
                while (curr.right != null) {
                    curr = curr.right;
                }

                curr.right = root.right;
                root.right = root.left;

                root.left = null;
            }
        }


    }

    //public void pre(TreeNode root, List<TreeNode> list) {
    //    if (root == null) {
    //        return;
    //    }
    //
    //
    //    list.add(root);
    //
    //    pre(root.left, list);
    //
    //    pre(root.right, list);
    //
    //}


    public int sumNumbers(TreeNode root) {
        //方法一：2ms
        //ArrayList<Integer> list = new ArrayList<>();
        //pre(root, 0, list);
        //Integer sum = list.stream().reduce(0, Integer::sum);
        //return sum;

        //方法二 0ms
        return pre(root, 0);
    }

    //public void pre(TreeNode root, int sum, List<Integer> list) {
    //
    //    sum = sum * 10 + root.val;
    //    //说明是叶子节点
    //    if (root.left == null && root.right == null) {
    //        list.add(sum);
    //    }
    //
    //
    //    if (root.left != null) {
    //
    //        pre(root.left, sum, list);
    //    }
    //
    //    if (root.right != null) {
    //        pre(root.right, sum, list);
    //    }
    //
    //}
    public int pre(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int temp = sum * 10 + root.val;

        //走到子叶节点，计算出每条路径组成的值，然后将其返回
        if (root.left == null && root.right == null) {

            return temp;
        }
        //将每条路径的值加起来
        return pre(root.left, temp) + pre(root.right, temp);

    }


    /**
     * 124. 二叉树中的最大路径和
     * 困难
     * 相关标签
     * 相关企业
     * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     * 路径和 是路径中各节点值的总和。
     * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
     *
     * @param root
     * @return
     */
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return max;
    }

    /**
     * 返回经过root的单边分支最大和， 即Math.max(root, root+left, root+right)
     * <p>
     * 思路：a 为根节点， b c 为左右节点
     * <p>
     * 三种方案：b - a - c      /  b - a - a的父结点   / c - a - a的父结点
     *
     * @param root
     * @return
     */
    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //值得注意，不取负数
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        //方案一 （当前路径）
        max = Math.max(max, root.val + left + right);
        //方案二   继续寻找路径
        //方案三
        return root.val + Math.max(left, right);
    }


    /**
     * 103. 二叉树的锯齿形层序遍历
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            LinkedList<Integer> temp = new LinkedList<>();
            while (size > 0) {
                TreeNode node = que.removeFirst();
                if (res.size() % 2 == 0) temp.addLast(node.val);
                else temp.addFirst(node.val);
                if (node.left != null) {
                    que.addLast(node.left);
                }

                if (node.right != null) {
                    que.addLast(node.right);
                }

                size--;
            }
            res.add(temp);
        }

        return res;

    }


    /**
     * 230. 二叉搜索树中第K小的元素
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
     *
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();

                if (--k == 0) {
                    return curr.val;
                }

                curr = curr.right;
            }

        }
        return 0;
    }


    /**
     * 212. 单词搜索 II
     * 困难
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
     * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
     *
     * @param board
     * @param words
     * @return
     */
    //方法一：超时
    //public List<String> findWords(char[][] board, String[] words) {
    //    List<String> res = new ArrayList<>();
    //
    //    if (board == null || board.length == 0) {
    //        return res;
    //    }
    //
    //    if (words == null || words.length == 0) {
    //        return res;
    //    }
    //
    //    for (int i = 0; i < words.length; i++) {
    //        match(board, words[i], res);
    //    }
    //
    //    return res;
    //}
    //
    //public void match(char[][] board, String word, List<String> res) {
    //    char op = word.charAt(0);
    //    for (int i = 0; i < board.length; i++) {
    //        for (int j = 0; j < board[i].length; j++) {
    //            String path = null;
    //            boolean[][] isVisit = new boolean[board.length][board[0].length];
    //            if (board[i][j] == op && (path = find(board, i, j, "", word, 0, isVisit)) != null) {
    //                //进行递归匹配
    //                res.add(path);
    //                return;
    //            }
    //        }
    //    }
    //}
    //
    //int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    //
    //public String find(char[][] board, int i, int j, String path, String word, int index, boolean[][] isVisit) {
    //    String res = null;
    //
    //
    //    if (board[i][j] == word.charAt(index)) {
    //        path = path + word.charAt(index);
    //        isVisit[i][j] = true;
    //        for (int m = 0; m < dir.length; m++) {
    //
    //            if (path.equals(word)) {
    //                return path;
    //            }
    //
    //            int x = dir[m][0];
    //            int y = dir[m][1];
    //            //四个方向进行查找
    //            //相等
    //            if ((i + x >= 0 && i + x < board.length) && (j + y >= 0 && j + y < board[0].length
    //                    && !isVisit[i + x][j + y])) {
    //                res = find(board, i + x, j + y, path, word, index + 1, isVisit);
    //            }
    //
    //            if (res != null) {
    //                return res;
    //            }
    //        }
    //        //回溯
    //        isVisit[i][j] = false;
    //        path = path.substring(0, path.length() - 1);
    //    }
    //
    //    return null;
    //}
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> ans = new HashSet<>();
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                dfs(board, trie, i, j, ans);
            }
        }

        return new ArrayList<String>(ans);
    }

    public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) {
        if (!now.children.containsKey(board[i1][j1])) {
            return;
        }
        char ch = board[i1][j1];
        now = now.children.get(ch);
        if (!"".equals(now.word)) {
            ans.add(now.word);
        }

        //什么情况下置于 '#' ?
        //访问过置于 '#' ， 防止重复访问
        board[i1][j1] = '#';
        for (int[] dir : dirs) {
            int i2 = i1 + dir[0], j2 = j1 + dir[1];
            if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) {
                dfs(board, now, i2, j2, ans);
            }
        }
        board[i1][j1] = ch;
    }


    class Trie {
        String word;
        Map<Character, Trie> children;
        boolean isWord;

        public Trie() {
            this.word = "";
            this.children = new HashMap<Character, Trie>();
        }

        public void insert(String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                if (!cur.children.containsKey(c)) {
                    cur.children.put(c, new Trie());
                }
                cur = cur.children.get(c);
            }
            cur.word = word;
        }

    }


    /**
     * 22. 括号生成
     * 中等
     * 相关标签
     * 相关企业
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * <p>
     * 思路：
     * 从选和不选的角度来做题
     * 因为括号是成对出现的，所以有 n 个左，就肯定有 n 个右，
     * 所以，如果提前选了 n 个左，后面就只能选 n 个右了
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        char[] path = new char[2 * n];
        dfs(0, 0, n, res, path);
        return res;

    }

    private void dfs(int i, int open, int n, List<String> res, char[] path) {
        if (i == 2 * n) {
            res.add(new String(path));
            return;
        }

        //选左括号 同时这里有个原则，只有左括号未满，左括号能选，就优先选左括号，这样就不会出现 不对等括号 情况的出现
        if (open < n) {
            path[i] = '(';
            dfs(i + 1, open + 1, n, res, path);
        }

        //不选左括号
        if (i - open < open) {
            path[i] = ')';
            dfs(i + 1, open, n, res, path);
        }
    }


    /**
     * 79. 单词搜索
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public boolean dfs(char[][] board, String word, int i, int j, int index) {
        char ch = board[i][j];
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        if (index == word.length() - 1) {
            return true;
        }

        board[i][j] = '#';
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];

            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
                if (dfs(board, word, x, y, index + 1)) {
                    return true;
                }
            }
        }
        board[i][j] = ch;

        return false;
    }


    /**
     * 52. N 皇后 II
     * 困难
     * 相关标签
     * 相关企业
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
     *
     * @param n
     * @return
     */
    int count = 0;

    public int totalNQueens(int n) {
        int[][] board = new int[n][n];
        dfs(board, 0);
        return count;
    }

    public void dfs(int[][] board, int index) {
        if (index == board.length) {
            count++;
            return;
        }

        for (int j = 0; j < board[index].length; j++) {
            if (!isInLine(board, index, j)) {
                board[index][j] = 1;
                dfs(board, index + 1);
                board[index][j] = 0;
            }
        }
    }


    /**
     * 判断是否在同一对角线 或 同一直线
     *
     * @param board
     * @param i
     * @param j
     * @return
     */
    public boolean isInLine(int[][] board, int i, int j) {

        for (int i1 = 0; i1 < i; i1++) {
            for (int j1 = 0; j1 < board[i1].length; j1++) {
                if (board[i1][j1] == 1 && (j == j1 || Math.abs(i - i1) == Math.abs(j - j1))) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 148. 排序链表
     * 中等
     * 相关标签
     * 相关企业
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * <p>
     * 归并排序
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //分
        ListNode fast = head.next;
        ListNode slow = head;
        //  找到中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        //治
        ListNode first = new ListNode(0);
        ListNode temp = first;
        while (left != null && right != null) {
            if (left.val > right.val) {
                temp.next = right;
                right = right.next;
            } else {
                temp.next = left;
                left = left.next;
            }
            temp = temp.next;
        }

        temp.next = left == null ? right : left;

        return first.next;

    }


    /**
     * 23. 合并 K 个升序链表
     * 困难
     * 相关标签
     * 相关企业
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        ListNode node = merge(lists, 0, lists.length - 1);
        return node;
    }

    private ListNode merge(ListNode[] lists, int left, int right) {

        if (left == right) {
            return lists[left];
        }
        //分
        int mind = (left + right) / 2;

        ListNode node1 = merge(lists, left, mind);
        ListNode node2 = merge(lists, mind + 1, right);

        //治
        ListNode first = new ListNode(0);
        ListNode temp = first;

        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                temp.next = node1;
                node1 = node1.next;
            } else {
                temp.next = node2;
                node2 = node2.next;
            }

            temp = temp.next;
        }

        temp.next = node1 == null ? node2 : node1;

        return first.next;

    }


    /**
     * 53. 最大子数组和
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 子数组
     * 是数组中的一个连续部分。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null) {
            return 0;
        }
        // dp[i] 表示前 i 个元素最大的子数组和为 dp[i]
        int[] dp = new int[nums.length];

        //确人递推公式
        //确认初始化
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    /**
     * 918. 环形子数组的最大和
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
     * 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
     * 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
     *
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular(int[] nums) {
        int total = nums[0], maxSum = nums[0], curMax = nums[0], minSum = nums[0], curMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            //计算最大连续子序列
            if (maxSum >= 0) {
                maxSum += nums[i];
            } else {
                maxSum = Math.max(maxSum, nums[i]);
            }
            curMax = Math.max(curMax, maxSum);

            //计算最小连续子序列
            if (minSum <= 0) {
                minSum += nums[i];
            } else {
                minSum = Math.min(minSum, nums[i]);
            }

            curMin = Math.min(curMin, minSum);

            total += nums[i];
        }

        return curMax > 0 ? Math.max(curMax, total - curMin) : curMax;
    }


    /**
     * 74. 搜索二维矩阵
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {


        int high = 0;
        int low = matrix.length - 1;

        while (low >= high) {
            int mid = (low + high) / 2;

            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                high = mid + 1;
            } else {
                low = mid - 1;
            }
        }


        if (low <= high) {
            int left = 0;
            if (low < 0) {
                low++;
            }
            int right = matrix[low].length - 1;

            while (left <= right) {
                int mid = (left + right) / 2;
                if (matrix[low][mid] == target) {
                    return true;
                } else if (matrix[low][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return false;
    }


    /**
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 2;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] > nums[mid + 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }


    /**
     * 33. 搜索旋转排序数组
     * 中等
     * 相关标签
     * 相关企业
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int mid = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                mid = i;
                break;
            }
        }

        int res1 = binarySearch(nums, 0, mid, target);
        int res2 = binarySearch(nums, mid + 1, nums.length - 1, target);

        return res1 == -1 ? res2 : res1;
    }

    public int binarySearch(int[] nums, int left, int right, int target) {
        int res = -1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                res = mid;
                break;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return res;
    }


    /**
     * 153. 寻找旋转排序数组中的最小值
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 2;

        while (left <= right) {
            int mid = (right + left) / 2;

            if (nums[mid] < nums[nums.length - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return nums[left];
    }


    /**
     * 215. 数组中的第K个最大元素
     * 中等
     * 相关标签
     * 相关企业
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        //小顶堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int num : nums) {
            priorityQueue.offer(num);

            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }

        return priorityQueue.poll();

    }


    /**
     * 快速排序
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int sort(int[] nums, int left, int right, int k) {
        int mid = nums[(right + left) / 2];

        int l = left;
        int r = right;
        int temp = 0;

        while (l < r) {
            while (nums[r] > mid) {
                r--;
            }

            while (nums[l] < mid) {
                l++;
            }

            if (l >= r) {
                break;
            }

            temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;

            if (nums[l] == mid) {
                r--;
            }

            if (nums[r] == mid) {
                l++;
            }
        }

        if (right - r == k - 1) {
            return nums[r];
        }

        int res = 0;
        //右排序
        if (right - r > k - 1) {
            res = sort(nums, r + 1, right, k);
        } else {
            res = sort(nums, left, r - 1, (k - 1) - (right - r));
        }

        return res;

    }


    /**
     * 373. 查找和最小的 K 对数字
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
     * 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
     * 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;

        // 预分配空间
        List<List<Integer>> ans = new ArrayList<>(k);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        pq.add(new int[]{nums1[0] + nums2[0], 0, 0});
        System.out.println("0, 0");

        while (!pq.isEmpty() && ans.size() < k) {
            int[] p = pq.poll();
            int i = p[1], j = p[2];
            ans.add(Arrays.asList(nums1[i], nums2[j]));

            if (j == 0 && i + 1 < n) {
                pq.add(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});
                System.out.print(i + 1  + ", " + 0 +  "     ");
            }

            if (j + 1 < m) {
                pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
                System.out.println(i + ", " + (j + 1));
            }

        }

        return ans;
    }


    /**
     *
     *502. IPO
     * 困难
     * 相关标签
     * 相关企业
     * 假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
     * 给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
     * 最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
     * 总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
     * 答案保证在 32 位有符号整数范围内。
     *
     * @param k
     * @param w
     * @param profits
     * @param capital
     * @return
     */
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int len = profits.length;
        int[][] arr = new int[len][2];

        for (int i = 0; i < len; i++) {
            // 需要资本
            arr[i][0] = capital[i];
            // 利润
            arr[i][1] = profits[i];
        }

        System.out.println();
        // 按资本从小到大排序
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        // 大顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int curr = 0;
        for (int i = 0; i < k; i++) {

            while (curr < len && w >= arr[curr][0]) {
                pq.offer(arr[curr][1]);
                curr++;
            }

            if (pq.isEmpty()) {
                break;
            } else {
                w += pq.poll();
            }
        }

        return w;
    }


    /**
     *
     * 67. 二进制求和
     * 简单
     * 相关标签
     * 相关企业
     * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();

        // 存在  1 + 1 = 2, 向前进一位的情况
        int temp = 0;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int sum = temp;

            if (i >= 0) {
                sum += a.charAt(i) - '0';
            }

            if (j >= 0) {
                sum += b.charAt(j) - '0';
            }

            ans.append(sum % 2);
            // 决定下一次循环，sum是 1 还是 0
            temp = sum / 2;
        }

        ans.append(temp == 1 ? "1" : "");

        return ans.reverse().toString();

    }


    /**
     *
     * 90. 颠倒二进制位
     * 简单
     * 相关标签
     * 相关企业
     * 颠倒给定的 32 位无符号整数的二进制位。
     * 提示：
     * 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
     * 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
     * @param n
     * @return
     *
     * 原数据为:12345678
     * 第一轮 奇偶位交换 21436587
     * 第二轮 每两位交换 43218765
     * 第三轮 每四位交换 87654321
     *
     *
     * 首先，我们知道 （单个二进制码 & 1) = 其本身，所以对于参数 M1，可以看成是用来将一串二进制码的奇数位提取出来；
     * 接着，n >> 1，右移，可以看作是将 n 上原来的偶数位变成奇数位，为什么不说奇数位也变成偶数位，是因为右移将第一个奇数位移除了；
     * 其次，(n >> 1) & M1，就是如1所述，将（n >> 1）的奇数位提取出来，也就是原 n 的偶数位；
     * 再次，(n & M1) << 1，就是先将 n 的奇数位提出来，然后左移，将其变成偶数位；
     * 然后，奇数位(原 n 的偶数位) | 偶数位(原 n 的奇数位)，相或，就达到了原 n 的奇数位和偶数位互换的目的；
     */
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
        n = n >>> 1 & M1 | (n & M1) << 1;
        n = n >>> 2 & M2 | (n & M2) << 2;
        n = n >>> 4 & M4 | (n & M4) << 4;
        n = n >>> 8 & M8 | (n & M8) << 8;
        return n >>> 16 | n << 16;
    }


    /**
     *
     * 191. 位1的个数
     * 简单
     * 相关标签
     * 相关企业
     * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中
     * 设置位
     *  的个数（也被称为汉明重量）。
     *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {

        int count = 0;
        while (n != 0) {

            if (n % 2 == 1) {
                count++;
            }

            n /= 2;
        }

        return count;
    }


    ///**
    // *
    // * 136. 只出现一次的数字
    // * 简单
    // * 相关标签
    // * 相关企业
    // * 提示
    // * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    // * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
    // *
    // * @param nums
    // * @return
    // */
    //public int singleNumber(int[] nums) {
    //
    //    int res = 0;
    //
    //    for (int num : nums) {
    //        res ^= num;
    //    }
    //
    //    return res;
    //}


    /**
     *
     *给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     * 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int num : nums) {
            if (map.get(num) == 1) {
                return num;
            }
        }
        return -1;
    }


    /**
     *
     * 201. 数字范围按位与
     * 中等
     * 相关标签
     * 相关企业
     * 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
     *
     * @param left
     * @param right
     * @return
     */
    public int rangeBitwiseAnd(int left, int right) {

        long sum = left;

        for (long i = (long) left + 1; i <= (long) right; i++) {
            sum &= i;

            if (sum == 0) {
                return 0;
            }
        }

        return (int) sum;
    }


    /**
     *
     * 9. 回文数
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     * 回文数
     * 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *
     * 例如，121 是回文，而 123 不是。
     *
     * @param x
     * @return
     */
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        int curr = 0;
        int temp = x;

        while (temp != 0) {
            curr = curr * 10 + temp % 10;

            temp /= 10;
        }


        return curr == x;
    }


    /**
     *
     * 66. 加一
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] += 1;
                break;
            }
        }

        if (digits[0] == 0) {
            int[] res = Arrays.copyOf(digits, digits.length + 1);
            res[0] = 1;
            return res;
        } else {
            return digits;
        }
    }


    /**
     *
     * 172. 阶乘后的零
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
     * 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
     *
     * @param n
     * @return
     */
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            count += n / 5;
            n = n / 5;
        }
        return count;

    }


    /**
     *
     * 50. Pow(x, n)
     * 中等
     * 相关标签
     * 相关企业
     * 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
     *
     *
     *
     * x *= x
     * x *= x
     * ....
     * 1, 2, 4, 6, 8, ...
     *
     * n /= 2
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        if (x == 0.0) {
            return x;
        }

        double res = 1.0;
        long b = n;

        if (n < 0) {
            x = 1 / x;
            b = -b;
        }

        while (b > 0) {
            if ((b & 1) == 1) {
                res *= x;
            }

            x *= x;
            n >>= 1;
        }

        return res;
    }


    @Test
    public void myTest() {
       myPow(2, -2);
    }


}
